/*
 * The following iterative sequence is defined for the set of positive integers:
 * 
 * n -> n/2 (n is even)
 * n -> 3n + 1 (n is odd)
 * 
 * Using the rule above and starting with 13, we generate the following sequence:
 * 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
 * 
 * It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
 * Although it has not been proved yet (Collatz Problem),
 * it is thought that all starting numbers finish at 1.
 * 
 * Which starting number, under one million, produces the longest chain?
 * 
 * NOTE: Once the chain starts the terms are allowed to go above one million.
 */

package pj1;

import java.util.HashMap;

class Problem14 {

	static final int problem = 1000000;
	static final Long ONE = new Long(1);

	public static void main(String[] args) {
		HashMap<Long, Long> chains = new HashMap<Long, Long>(problem);

		Long count = ONE, chain = ONE, n = ONE;
		Integer result = 0;
		
		// pre-fill one
		chains.put(n.longValue(), chain.longValue());
		
		for (Integer i = 2; i < problem; i++) {
			count = new Long(0);
			n = new Long(i);

			while (true) {
				if (chains.containsKey(n)) {
					count += chains.get(n).intValue();
					break;
				}
				n = (n%2 == 1) ? 3*n+1 : n/2;
				count++;
			}
			chains.put(i.longValue(), count.longValue());
			
			if (count > chain) {
				result = i;
				chain = count;
			}
		}
		System.out.println(result);
	}
}
